home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 1997: The Complete Utilities Toolkit / macworld-complete-utilities-1997.iso / Programming / Little Smalltalk v3.1.5 / C Source / Sources / memory.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-01-26  |  10.9 KB  |  474 lines  |  [TEXT/KAHL]
  1. /*
  2.     Little Smalltalk, version 2
  3.     Written by Tim Budd, Oregon State University, July 1987
  4.  
  5.     Improved incorporating suggestions by 
  6.         Steve Crawley, Cambridge University, October 1987
  7.         Steven Pemberton, CWI, Amsterdam, Oct 1987
  8.  
  9.     memory management module
  10.  
  11.     This is a rather simple, straightforward, reference counting scheme.
  12.     There are no provisions for detecting cycles, nor any attempt made
  13.     at compaction.  Free lists of various sizes are maintained.
  14.     At present only objects up to 255 bytes can be allocated, 
  15.     which mostly only limits the size of method (in text) you can create.
  16.  
  17.     reference counts are not stored as part of an object image, but
  18.     are instead recreated when the object is read back in.
  19.     This is accomplished using a mark-sweep algorithm, similar
  20.     to those used in garbage collection.
  21.  
  22.     Function swapObjects () added by Julian Barkway, Nov. 1994, to support 
  23.     the 'become:' method in class Object.
  24. */
  25.  
  26. # include <stdio.h>
  27. # include <stdlib.h>
  28.  
  29. # ifdef LIGHTC
  30. # include <unix.h>
  31. # include <storage.h>
  32. # include <proto.h>
  33. # endif
  34.  
  35. # include "env.h"
  36. # include "memory.h"
  37.  
  38. # include <string.h>
  39. # ifdef STRING
  40. # include <string.h>
  41. # endif
  42. # ifdef STRINGS
  43. # include <strings.h>
  44. # endif
  45.  
  46. # ifdef ALLOC
  47. # include <alloc.h>
  48. # endif
  49. #ifdef THINKC
  50. # include "memory.proto.h"
  51. # ifdef TCL
  52. #   include "tclprim.proto.h"
  53. # else
  54. #   include "winprim.proto.h"
  55. # endif
  56. #else
  57. # ifndef ALLOC
  58. extern char *calloc();
  59. # endif
  60. #endif
  61.  
  62.  
  63. boolean debugging = false;
  64. object sysobj;    /* temporary used to avoid rereference in macros */
  65. object intobj;
  66.  
  67. object symbols;        /* table of all symbols created */
  68.  
  69. /*
  70.     in theory the objectTable should only be accessible to the memory
  71.     manager.  Indeed, given the right macro definitions, this can be
  72.     made so.  Never the less, for efficiency sake some of the macros
  73.     can also be defined to access the object table directly
  74.  
  75.     Some systems (e.g. the Macintosh) have static limits (e.g. 32K)
  76.     which prevent the object table from being declared.
  77.     In this case the object table must first be allocated via
  78.     calloc during the initialization of the memory manager.
  79. */
  80.  
  81. # ifdef obtalloc
  82. struct objectStruct *objectTable;
  83. # endif
  84. # ifndef obtalloc
  85. struct objectStruct objectTable[ObjectTableMax];
  86. # endif
  87.  
  88. /*
  89.     The following variables are strictly local to the memory
  90.     manager module
  91.  
  92.     FREELISTMAX defines the maximum size of any object.
  93. */
  94.  
  95. # define FREELISTMAX 2000
  96. static object objectFreeList[FREELISTMAX];/* free list of objects */
  97.  
  98. # ifndef mBlockAlloc
  99.  
  100. # define MemoryBlockSize 6000
  101.         /* the current memory block being hacked up */
  102. static object *memoryBlock;        /* malloc'ed chunck of memory */
  103. static int    currentMemoryPosition;    /* last used position in above */
  104. # endif
  105.  
  106.  
  107. /* initialize the memory management module */
  108. noreturn initMemoryManager(void) {
  109.     int i;
  110.  
  111. # ifdef obtalloc
  112.     objectTable = obtalloc(ObjectTableMax, sizeof(struct objectStruct));
  113.     if (! objectTable)
  114.         sysError("cannot allocate","object table");
  115. # endif
  116.  
  117.     /* set all the free list pointers to zero */
  118.     for (i = 0; i < FREELISTMAX; i++)
  119.         objectFreeList[i] = nilobj;
  120.  
  121.     /* set all the reference counts to zero */
  122.     for (i = 0; i < ObjectTableMax; i++) {
  123.         objectTable[i].referenceCount = 0;
  124.         objectTable[i].size = 0;
  125.         }
  126.  
  127.     /* make up the initial free lists */
  128.     setFreeLists();
  129.  
  130. # ifndef mBlockAlloc
  131.     /* force an allocation on first object assignment */
  132.     currentMemoryPosition = MemoryBlockSize + 1;
  133. # endif
  134.  
  135.     /* object at location 0 is the nil object, so give it nonzero ref */
  136.     objectTable[0].referenceCount = 1;
  137.     objectTable[0].size = 0;
  138. }
  139.  
  140. /* setFreeLists - initialise the free lists */
  141. void setFreeLists(void) {
  142.     int i, size;
  143.     register int z;
  144.     register struct objectStruct *p;
  145.  
  146.     objectFreeList[0] = nilobj;
  147.  
  148.     for (z=ObjectTableMax-1; z>0; z--) {
  149.         if (objectTable[z].referenceCount == 0){
  150.             /* Unreferenced, so do a sort of sysDecr: */
  151.             p= &objectTable[z];
  152.             size = p->size;
  153.             if (size < 0) size = ((-size) + 1)/2;
  154.             p->class = objectFreeList[size];
  155.             objectFreeList[size]= z;
  156.             for (i= size; i>0; )
  157.                 p->memory[--i] = nilobj;
  158.             }
  159.         }
  160. }
  161.  
  162. /*
  163.   mBlockAlloc - rip out a block (array) of object of the given size from
  164.     the current malloc block 
  165. */
  166. # ifndef mBlockAlloc
  167.  
  168. object *mBlockAlloc(int memorySize)
  169. {    object *objptr;
  170.  
  171.     if (currentMemoryPosition + memorySize >= MemoryBlockSize) {
  172.         
  173.         /* we toss away space here.  Space-Frugal users may want to
  174.         fix this by making a new object of size
  175.         MemoryBlockSize - currentMemoryPositon - 1
  176.         and putting it on the free list, but I think
  177.         the savings is potentially small */
  178. #ifdef THINK_C
  179.         memoryBlock = (object *) calloc((size_t) MemoryBlockSize, (size_t)sizeof(object));
  180. #else
  181.         memoryBlock = (object *) calloc((unsigned) MemoryBlockSize, sizeof(object));
  182. #endif
  183.         if (! memoryBlock)
  184.             sysError("out of memory","malloc failed");
  185.         currentMemoryPosition = 0;
  186.         }
  187.     objptr = (object *) &memoryBlock[currentMemoryPosition];
  188.     currentMemoryPosition += memorySize;
  189.     return(objptr);
  190. }
  191. # endif
  192.  
  193. /* allocate a new memory object */
  194. object allocObject(int memorySize)
  195. {    int i;
  196.     register int position;
  197.     boolean done;
  198.  
  199.     if (memorySize >= FREELISTMAX) {
  200.         fprintf(stderr,"size %d\n", memorySize);
  201.         sysError("allocation bigger than permitted","allocObject");
  202.         }
  203.  
  204.     /* first try the free lists, this is fastest */
  205.     if ((position = objectFreeList[memorySize]) != 0) {
  206.         objectFreeList[memorySize] = objectTable[position].class;
  207.         }
  208.  
  209.     /* if not there, next try making a size zero object and
  210.         making it bigger */
  211.     else if ((position = objectFreeList[0]) != 0) {
  212.         objectFreeList[0] = objectTable[position].class;
  213.         objectTable[position].size = memorySize;
  214.         objectTable[position].memory = mBlockAlloc(memorySize);
  215.         }
  216.  
  217.     else {        /* not found, must work a bit harder */
  218.         done = false;
  219.  
  220.         /* first try making a bigger object smaller */
  221.         for (i = memorySize + 1; i < FREELISTMAX; i++)
  222.             if ((position = objectFreeList[i]) != 0) {
  223.                 objectFreeList[i] = objectTable[position].class;
  224.                 /* just trim it a bit */
  225.                 objectTable[position].size = memorySize;
  226.                 done = true;
  227.                 break;
  228.                 }
  229.  
  230.         /* next try making a smaller object bigger */
  231.         if (! done)
  232.             for (i = 1; i < memorySize; i++)
  233.                 if ((position = objectFreeList[i]) != 0) {
  234.                     objectFreeList[i] =
  235.                         objectTable[position].class;
  236.                     objectTable[position].size = memorySize;
  237. # ifdef mBlockAlloc
  238.                     free(objectTable[position].memory);
  239. # endif
  240.                     objectTable[position].memory = 
  241.                         mBlockAlloc(memorySize);
  242.                     done = true;
  243.                     break;
  244.                     }
  245.  
  246.         /* if we STILL don't have it then there is nothing */
  247.         /* more we can do */
  248.         if (! done)
  249.             sysError("out of objects","alloc");
  250.         }
  251.  
  252.     /* set class and type */
  253.     objectTable[position].referenceCount = 0;
  254.     objectTable[position].class = nilobj;
  255.     objectTable[position].size = memorySize;
  256.     return(position << 1);
  257. }
  258.  
  259. object allocByte(int size)
  260. {    object newObj;
  261.  
  262.     newObj = allocObject((size + 1) / 2);
  263.     /* negative size fields indicate bit objects */
  264.     sizeField(newObj) = - size;
  265.     return newObj;
  266. }
  267.  
  268. object allocStr(char *str)
  269. {    register object newSym;
  270.  
  271.     newSym = allocByte(1 + strlen(str));
  272.     ignore strcpy(charPtr(newSym), str);
  273.     return(newSym);
  274. }
  275.  
  276. # ifdef incr
  277. object incrobj;        /* buffer for increment macro */
  278. # endif
  279. # ifndef incr
  280. void incr(object z)
  281. {
  282.     if (z && ! isInteger(z)) {
  283.         objectTable[z>>1].referenceCount++;
  284.         }
  285. }
  286. # endif
  287.  
  288. # ifndef decr
  289. void decr(object z)
  290. {
  291.     if (z && ! isInteger(z)) {
  292.         if (--objectTable[z>>1].referenceCount <= 0) {
  293.             sysDecr(z);
  294.             }
  295.         }
  296. }
  297. # endif
  298.  
  299. /* do the real work in the decr procedure */
  300. void sysDecr(object z)
  301. {    register struct objectStruct *p;
  302.     register int i;
  303.     int size;
  304. if (z == 12596) {
  305. i = 1;
  306. }
  307.     p = &objectTable[z>>1];
  308.     if (p->referenceCount < 0) {
  309.         fprintf(stderr,"object %d\n", z);
  310.         sysError("negative reference count","");
  311.         }
  312.     decr(p->class);
  313.     size = p->size;
  314.     if (size < 0) size = ((- size) + 1) /2;
  315.     p->class = objectFreeList[size];
  316.     objectFreeList[size] = z>>1;
  317.     if (size > 0) {
  318.         if (p->size > 0)
  319.             for (i = size; i; )
  320.                 decr(p->memory[--i]);
  321.         for (i = size; i > 0; )
  322.             p->memory[--i] = nilobj;
  323.         }
  324.     p->size = size;
  325. }
  326.  
  327. # ifndef basicAt
  328. object basicAt(object z, int i)
  329. {
  330.     if (isInteger(z))
  331.         sysError("attempt to index","into integer");
  332.     else if ((i <= 0) || (i > sizeField(z))) {
  333.         ignore fprintf(stderr,"index %d size %d\n", i, (int) sizeField(z));
  334.         sysError("index out of range","in basicAt");
  335.         }
  336.     else
  337.         return(sysMemPtr(z)[i-1]);
  338.     return(0);
  339. }
  340. # endif
  341.  
  342. # ifndef simpleAtPut
  343.  
  344. void simpleAtPut(object z, int i, object v)
  345. {
  346.     if (isInteger(z))
  347.         sysError("assigning index to","integer value");
  348.     else if ((i <= 0) || (i > sizeField(z))) {
  349.         ignore fprintf(stderr,"index %d size %d\n", i, (int) sizeField(z));
  350.         sysError("index out of range","in basicAtPut");
  351.         }
  352.     else {
  353.         sysMemPtr(z)[i-1] = v;
  354.         }
  355. }
  356. # endif
  357.  
  358. # ifndef basicAtPut
  359.  
  360. void basicAtPut(object z, int i, object v)
  361. {
  362.     simpleAtPut(z, i, v); 
  363.     incr(v);
  364. }
  365. # endif
  366.  
  367. # ifdef fieldAtPut
  368. int f_i;
  369. # endif
  370.  
  371. # ifndef fieldAtPut
  372. void fieldAtPut(object z, int i, object v)
  373. {
  374.     decr(basicAt(z, i)); basicAtPut(z, i, v);
  375. }
  376. # endif
  377.  
  378. # ifndef byteAt
  379. int byteAt(object z, int i)
  380. {    byte *bp;
  381.     unsigned char t;
  382.  
  383.     if (isInteger(z))
  384.         sysError("indexing integer","byteAt");
  385.     else if ((i <= 0) || (i > 2 * - sizeField(z))) {
  386.         fprintf(stderr,"index %d size %d\n", i, sizeField(z));
  387.         sysError("index out of range","byteAt");
  388.         }
  389.     else {
  390.         bp = bytePtr(z);
  391.         t = bp[i-1];
  392. fprintf(stderr,"byte at %d returning %d\n", i, (int) t);
  393.         i = (int) t;
  394.         }
  395.     return(i);
  396. }
  397. # endif
  398.  
  399. # ifndef byteAtPut
  400. void byteAtPut(object z, int i, int x)
  401. {    byte *bp;
  402.  
  403.     if (isInteger(z))
  404.         sysError("indexing integer","byteAtPut");
  405.     else if ((i <= 0) || (i > 2 * - sizeField(z))) {
  406. fprintf(stderr,"index %d size %d\n", i, sizeField(z));
  407.         sysError("index out of range", "byteAtPut");
  408.         }
  409.     else {
  410.         bp = bytePtr(z);
  411.         bp[i-1] = x;
  412.         }
  413. }
  414. # endif
  415.  
  416. /*
  417. Written by Steven Pemberton:
  418. The following routine assures that objects read in are really referenced,
  419. eliminating junk that may be in the object file but not referenced.
  420. It is essentially a marking garbage collector algorithm using the 
  421. reference counts as the mark
  422. */
  423.  
  424. void visit(object x)
  425. {
  426.     int i, s;
  427.     object *p;
  428.  
  429.     if (x && !isInteger(x)) {
  430.         if (++(objectTable[x>>1].referenceCount) == 1) {
  431.             /* then it's the first time we've visited it, so: */
  432.             visit(objectTable[x>>1].class);
  433.             s = sizeField(x);
  434.             if (s>0) {
  435.                 p = objectTable[x>>1].memory;
  436.                 for (i=s; i; --i) visit(*p++);
  437.                 }
  438.             }
  439.         }
  440. }
  441.  
  442. int objectCount(void)
  443. {    register int i, j;
  444.     j = 0;
  445.     for (i = 0; i < ObjectTableMax; i++)
  446.         if (objectTable[i].referenceCount > 0)
  447.             j++;
  448.     return j;
  449. }
  450.  
  451. /*
  452.     This routine swaps the positions of two objects so that object A 
  453.     'becomes' object B and vice-versa.
  454.      
  455.     Written by Julian Barkway in order to implement the Array/grow method
  456.     in a more ST-80 compatible way.
  457. */
  458. void swapObjects (object obj1, object obj2)
  459. {
  460.     struct objectStruct        tmp;
  461.     
  462.     tmp.class  = classField (obj1);
  463.     tmp.size   = sizeField  (obj1);
  464.     tmp.memory = sysMemPtr  (obj1); 
  465.  
  466.     sizeField  (obj1) = sizeField  (obj2);
  467.     classField (obj1) = classField (obj2);
  468.     sysMemPtr  (obj1) = sysMemPtr  (obj2);  
  469.     
  470.     sizeField  (obj2) = tmp.size;
  471.     classField (obj2) = tmp.class;
  472.     sysMemPtr  (obj2) = tmp.memory;  
  473. }
  474.